package astar 
{
	/**
	 * AStar 算法
	 * @author StefanieKaka
	 */
	public class AStar 
	{
		/// 曼哈顿启发式
		public static const MANHATTAN		: String = "ManHattan";
		
		/// 欧几里德几何式
		public static const EUCLIDIAN		: String = "Euclidian";
		
		/// 对角启发式
		public static const DIAGONAL		: String = "Diagonal";
		
		/// 构造函数
		public function AStar() 
		{
		}
		
///////////////////////////////////////////////////////////////////////////////////////////////////
// 公共域
///////////////////////////////////////////////////////////////////////////////////////////////////
		
		/// 寻找路径
		public function findPath(grid : Grid, heuristic : String = MANHATTAN) : Boolean
		{
			m_grid = grid;
			m_open = new Vector.<Node>();
			m_closed = new Vector.<Node>();
			
			m_startNode = m_grid.startNode;
			m_endNode = m_grid.endNode;
			
			switch (heuristic)
			{
				case MANHATTAN:
					m_heuristic = manhattan;
					break;
					
				case EUCLIDIAN:
					m_heuristic = euclidian;
					break;
					
				case DIAGONAL:
					m_heuristic = diagonal;
					break;
			}
			
			m_startNode.g = 0;
			m_startNode.h = m_heuristic(m_startNode);
			m_startNode.f = m_startNode.g + m_startNode.h;
			
			return search();
		}
		
		/// 搜索路径
		public function search() : Boolean
		{
			var node : Node = m_startNode;
			
			while (node != m_endNode)
			{
				// 得到当前节点周围的格子索引
				var startX : int = Math.max(0, node.x - 1);
				var endX : int = Math.min(m_grid.cols - 1, node.x + 1);
				var startY : int = Math.max(0, node.y - 1);
				var endY : int = Math.min(m_grid.rows - 1, node.y + 1);
				
				for (var i : int = startX; i <= endX; ++i)
				{
					for (var j : int = startY; j <= endY; ++j)
					{
						// 获得测试节点
						var test : Node = m_grid.getNode(i, j);
						
						// 如果是当前节点 or 不能行走点, 则循环下一个循环
						if (test == node || !test.walkable)
							continue;
						
						// 计算代价, 在斜角是1.4, 否则是1
						var cost : Number = STRAIGHT_COST;
						if (!((node.x == test.x) || (node.y == test.y)))
						{
							if (!m_grid.getNode(node.x, test.y).walkable || !m_grid.getNode(test.x, node.y).walkable)
								continue;
							cost = DIAGONAL_COST;
						}
						
						var g : Number = node.g + cost;
						var h : Number = m_heuristic(test);
						var f : Number = g + h;
						
						if (isOpen(test) || isClosed(test))
						{
							// 如果当前代价小于上一次的代价, 那么将更新
							if (test.f > f)
							{
								test.f = f;
								test.g = g;
								test.h = h;
								test.parent = node;
							}
						}
						else
						{
							// 保存 f, g, h, 放入到待查列表中
							test.f = f;
							test.g = g;
							test.h = h;
							test.parent = node;
							m_open.push(test);
						}
					}
				}
				
				// 当前节点放入已查列表
				m_closed.push(node);
				
				// 待查列表中没有节点, 表示 start -> end 没有路径
				if (m_open.length == 0)
					return false;
					
				// 按 f 值, 从小到大排序
				m_open.sort(compare);
				
				// 从待查列表取出 f 值最小的节点
				node = m_open.shift();
			}
			
			// 创建路径
			buildPath();
			return true;
		}

		/// 获得路径
		public function get path() : Vector.<Node>
		{
			return m_path;
		}
		
		public function get visited() : Vector.<Node>
		{
			return m_closed.concat(m_open);
		}
		
///////////////////////////////////////////////////////////////////////////////////////////////////
// 私有域
///////////////////////////////////////////////////////////////////////////////////////////////////
		
		/// 判断是否在待查列表中
		private function isOpen(node : Node) : Boolean
		{
			return m_open.indexOf(node) != -1;
		}
		
		/// 判断是否在已经列表中
		private function isClosed(node : Node) : Boolean
		{
			return m_closed.indexOf(node) != -1;
		}
		
		/// 比较两个节点的代价
		private function compare(node1 : Node, node2 : Node) : Number
		{
			return node1.f - node2.f;
		}

		/// 从结束节点开始回溯到起始节点, 生成路径
		private function buildPath() : void
		{
			m_path = new Vector.<Node>();
			var node : Node = m_endNode;
			m_path.push(node);
			
			while (node != m_startNode)
			{
				node = node.parent;
				m_path.unshift(node);	// 添加到数组开头
			}
		}
		
		/// 曼哈顿式启发
		private function manhattan(node : Node) : Number
		{
			return Math.abs(node.x - m_endNode.x) * STRAIGHT_COST +
					Math.abs(node.y - m_endNode.y) * STRAIGHT_COST; 
		}
		
		/// 欧几里德启发式
		private function euclidian(node : Node) : Number
		{
			var dx : Number = node.x - m_endNode.x;
			var dy : Number = node.y - m_endNode.y;
			return Math.sqrt(dx * dx + dy * dy) * STRAIGHT_COST;
		}
		
		/// 对角启发式
		private function diagonal(node : Node) : Number
		{
			var dx : Number = Math.abs(node.x - m_endNode.x);
			var dy : Number = Math.abs(node.y - m_endNode.y);
			var diag : Number = Math.min(dx, dy);
			var straight : Number = dx + dy;
			return DIAGONAL_COST * diag + STRAIGHT_COST * (straight - 2 * diag);
		}

		private var m_open		: Vector.<Node> = null;		// 待查列表
		private var m_closed	: Vector.<Node> = null;		// 已查列表
		private var m_grid		: Grid = null;
		private var m_endNode	: Node = null;
		private var m_startNode	: Node = null;
		private var m_path		: Vector.<Node> = null;		// 经过路径
		private var m_heuristic	: Function = null;			// 启发函数
		
		private static const STRAIGHT_COST : Number = 1.0;
		private static const DIAGONAL_COST : Number = Math.SQRT2;
	}

}